// 有 n 个城市，其中一些彼此相连，另一些没有相连。
// 如果城市 a 与城市 b 直接相连，且城市 b 与城市 c 直接相连，那么城市 a 与城市 c 间接相连。
// 省份 是一组直接或间接相连的城市，组内不含其他没有相连的城市。

// 给你一个 n x n 的矩阵 isConnected ，其中 isConnected[i][j] = 1 
// 表示第 i 个城市和第 j 个城市直接相连，而 isConnected[i][j] = 0 表示二者不直接相连。

// 返回矩阵中 省份 的数量。


const findCircleNum = function (isConnected: number[][]): number {
    // 安全检测
    if (isConnected.length < 1) {
        return 0;
    }
    const isVisited: boolean[] = new Array(isConnected.length).fill(false);// 对应下标表示城市
    let provinces: number = 0;
    for (let i = 0; i < isConnected.length; i++) {
        // 如果当前城市没有被访问过
        if (isVisited[i] === false) {
            findCircleNumDFS(isConnected, isVisited, i);
            provinces++;
        }
    }
    return provinces;
};

// 深度优先遍历辅助方法，负责找到一个城市对应的所有联通分量
function findCircleNumDFS(isConnected: number[][], isVisited: boolean[], originI: number) {
    isVisited[originI] = true;// 将当前城市标记为已访问
    for (let j = 0; j < isConnected[0].length; j++) {
        // 如果当前矩阵值存在联通且该城市未被访问过
        if (isConnected[originI][j] === 1 && isVisited[j] === false) {
            findCircleNumDFS(isConnected, isVisited, j);
        }
    }
}

// 这道题目事实上是一道图论中比较典型的考题
// 先把 n 个城市和它们之间的相连关系看成图，
// 城市是图中的节点， 相连关系是图中的边， 给定的矩阵
// isConnected 即为图的邻接矩阵， 省份即为图中的连通分量。
// 而计算省份总数， 等价于计算图中的连通分量数， 可以通过深度优先搜索实现，
// 深度优先搜索的思路是很直观的， 首先声明一个访问矩阵（ 下标则依次代表对应城市）
// 遍历所有城市， 对于每个城市， 如果该城市尚未被访问过， 则从该城市开始深度优先搜索
// 通过矩阵isConnected 得到与该城市直接相连的城市有哪些， 这些城市和该城市属于同一个连通分量
// 然后对这些城市继续深度优先搜索， 直到同一个连通分量的所有城市都被访问到， 即可得到一个省份。
// 遍历完全部城市以后， 即可得到连通分量的总数， 即省份的总数。